package algorithm_demo.demo04;

import java.util.*;

/**
 * 贪心算法
 * 给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果
 * <p>
 * 思路
 * 将字符序列排序，排序的规则就是，如果a拼b 小于 b拼a，就将a放到前面；
 * 然后遍历整个排好序的字符串直接拼接，就是贪心后的字典序最小的字符串
 *
 * @author Api
 * @date 2023/2/12 23:43
 */
public class Code01_LowestLexicography {
    /*
    先给数组按照字典序排序，然后依次拼起来，适用于大多数case，但是个别如：ba,b 会拼成bba，但是bab实际上字典序更小，也就是
    两个字符串x,y
    x 的字典序 小于等于 y 的，那么x 放在前面，否则，y放前面
    改进：
    x 拼上 y 小于等于 y拼上x ，那么 x 放前面，否则, y 放前面
    全排列枚举：
    */
    //暴力解，全排列
    public static String lowestString1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        List<String> all = new ArrayList<>();
        Set<Integer> use = new HashSet<>();
        process(strs, use, "", all);
        String lowest = all.get(0);
        for (int i = 1; i < all.size(); i++) {
            if (all.get(i).compareTo(lowest) < 0) {
                lowest = all.get(i);
            }
        }
        return lowest;
    }

    // strs 里放着所有的字符串
    // 已经使用过的字符串的下标，在use里登记了，不要再使用了
    // 之前使用过的字符串，拼接成了 path
    // 用all 收集所有可能的拼接结果
    public static void process(String[] strs, Set<Integer> use, String path, List<String> all) {
        if (use.size() == strs.length) {
            all.add(path);
        } else {
            for (int i = 0; i < strs.length; i++) {
                if (!use.contains(i)) {
                    use.add(i);
                    process(strs, use, path + strs[i], all);
                    use.remove(i);
                }
            }
        }
    }


    //----------------------------------贪心算法------------------------------------
    //自定义比较器
    public static class MyComparator implements Comparator<String> {

        @Override
        public int compare(String o1, String o2) {
            return (o1 + o2).compareTo(o2 + o1);// 最小
            //return (o2 + o1).compareTo(o1 + o2); 最大
        }
    }

    //贪心算法
    public static String lowestString2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        Arrays.sort(strs, new MyComparator());
        String res = "";
        for (String str : strs) {
            res += str;
        }
        return res;
    }

    public static void main(String[] args) {
        String[] strs = {"a", "c", "ee", "hi", "cd"};
        String s = lowestString2(strs);
        System.out.println("贪心算法lowestString2: " + s);
        String s1 = lowestString1(strs);
        System.out.println("暴力全排列lowestString1: " + s1);
    }
}
